A multiprocessor system is typically any class of computer systems that utilizes more than one processor to execute instructions or perform operations. In most multiprocessor systems there are common resources in which the processors must rely, such as memory and input/output devices. When processors contend for such resources, the processors typically send requests to the common resource requesting that the common resource perform some type of transaction, such as performing a read operation, a write operation, or some other processing operation. Ideally, the common resource will immediately execute the requests as the requests are received. However, in most cases, the common resource will receive a large volume of requests at nearly the same time and cannot immediately process the requests.
Many approaches have been developed to attempt to solve this problem. For instance, one common solution is for the common resource to buffer all incoming requests and service them in the order they are received (or some other order depending on priority of the requests). The problem with this approach is that as the number of processors used in larger multiprocessor systems increase the number of outstanding requests also tends to increase, sometimes exponentially, making the buffer size too large, expensive, and impractical to implement for many applications.
Another common approach is to use a controller to control access to the common resource. For example, a controller, acting on behalf of the common resource, may notify certain requesters to retry their requests at a later time, because the common resource is currently unable to immediately process their requests (i.e., the common resource may be too busy or there may be a conflict). The problem with this approach is that the controller may unintentionally deny a particular transaction from continually being processed. In other words, a situation may arise in which a particular transaction, under certain circumstances, may continually get retried and cease to make forward progress, thus permanently preventing the system or a portion of the system from making forward progress, known as a “live-lock.”
Most controllers designed today attempt to prevent a live-lock situation from occurring by using a protocol that guarantees fairness of multiple transactions. Often these protocols are very complicated, expensive to implement, and must be custom-designed on a system-by-system basis. Additionally, many such controllers are prone to glitches and fail to guarantee fairness of transactions between multiple requesters, inadvertently enabling a live-lock situation to occur, among other problems.